Computer-aided methods are commonly employed for describing and analyzing the geometry of objects to be modeled and/or manufactured. While the descriptions of such objects are often generated within a computational solid modeling environment, it is also common to attempt to "import" an existing physical object into the solid modeling environment. For example, a visualization may be desired that incorporates a physical object in a computer-generated scene, or a solid model of an existing physical object may be desired to enable reproduction of the object using computer-aided manufacturing techniques. Representing the object within the solid modeling environment also allows computer-aided modifications to be performed. For example, scale models and mirror images of existing parts can be produced, and other solid modeling operations can be performed to add, remove, or modify features.
Importing the object into the modeling environment corresponds to creating a representation within the modeling environment, which corresponds to the object to be imported. This importing procedure often occurs in two steps. A collection of data points on the surface of the object is obtained (often by employing some form of scanning or coordinate measurement technology), and a solid model is constructed to fit the data. Due to the nature of many scanning devices, the surface point data are often arranged in layers or slices, and associated with each data point is an indication of the side of the point on which the object lies. This direction indication may be provided by a measurement of the surface normal at the data point or deduced from the location of the scanning device or proximal data points.
Prior art reconstruction algorithms can be broadly categorized into either surface reconstruction schemes or volume reconstruction schemes. Surface reconstruction schemes produce a surface model, usually a polygonal mesh, that closely approximates the data. One of the disadvantages of surface representation schemes is that they typically require such massive amounts of data for the vertices, edges, and faces that the storage, transmission, and modeling operations using that data become relatively expensive. Volume reconstruction schemes generate models that can be stored as a collection of primitives that are combined to produce the reconstructed object. An advantage of the volume reconstruction approach is that it produces a solid model that can easily be used or combined with other solid models to create more sophisticated shapes. The number of primitives is usually much smaller than the number of data points so that data compression is achieved and less data storage is required than in the surface reconstruction schemes.
Early reconstruction schemes involved connecting polyline planar contours to produce polygonal surface mosaics. Others have surveyed existing algorithms for cross-sectional surface reconstruction, provided a testbed for evaluating these techniques, and presented improvements on the initial divide-and-conquer approach. All of these prior art algorithms require that vertices forming one layer be paired with vertices on adjacent layers to determine the surface connectivity. One prior art technique employs smooth surface representations based on subdivision to reconstruct models from scattered range data. This procedure effectively produces accurate surface models from dense data, but the computations required are expensive (time consuming even on powerful computers). Another scheme involves the pruning of Delaunay tetrahedra to handle general topologies. This second approach generates the volume of the object (rather than just its surface) as a collection of tetrahedra. Attempts to reconstruct volumetric shape descriptions using implicit functions include a nonlinear least squares minimization method that produces superquadric models, a method for reconstructing superquadric models from laser range finder data, and a "blobby" approach in which a single initial primitive is repeatedly subdivided and optimized to produce an implicit function that approximates the data.
The methods that connect the points in a data layer to form surfaces run into difficulties determining how to connect points on one layer to those on adjacent layers. The problem of determining this point-to-point correspondence between layers becomes greater with an increasing size of the data set, since the prior art techniques don't scale well and often require human intervention to resolve difficult cases. The task of connecting the points properly between adjacent layers becomes especially problematic when the layers have different topology (different numbers of connected components and/or holes). The use of Delaunay tetrahedra to approximate the volume and establish data connectivity provides a partial solution to the problem; however, the method produces tetrahedral solids that cannot accurately represent objects with smooth surfaces, and the high probability of geometric degeneracy makes Delaunay triangulation of layered data sets problematic. Other methods are limited to superquadric surfaces and require independent knowledge of the surface topology. The blobby approach is computationally expensive, may fail on certain classes of data, and is not well suited to reconstructing objects with sharp edges. Each of the methods listed above is not appropriate for dealing with layered data. Still another prior art approach employs range data to produce a probabilistic spatial occupancy model.
A technique that is an extension of the method using Delaunay tetrahedra to approximate the layered volume of an object and to establish data connectivity between layers solves the above noted problems with the prior art. Clearly, it would be desirable to automatically determine the necessary connectivity information, both for data within a single layer and between adjacent layers, and to construct a corresponding representation in the form of an implicit function possessing a level set that lies close to the data points representing the object.